package LeetCode_118;



import java.util.ArrayList;

import java.util.List;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/10/11 20:56
 */
public class Solution {
    public List<List<Integer>> generate(int numRows){
        if(numRows==0){
            return new ArrayList<>();
        }
        List<List<Integer>> ans = new ArrayList<>();
        ans.add(new ArrayList<>());
        ans.get(0).add(1);
        if(numRows==1){
            return ans;
        }
        ans = new ArrayList<>();
        ans.add(new ArrayList<>());
        ans.add(new ArrayList<>());
        ans.get(0).add(1);
        ans.get(1).add(1);
        ans.get(1).add(1);
        if(numRows==2){
            return ans;
        }
        for (int i = 3; i <= numRows ; i++) {
            //+一行
            List<Integer> curLine = new ArrayList<>();
            ans.add(curLine);
            //第一个为 1
            ans.get(i-1).add(1);
            //处理最后一个以外的元素
            //这是第i行，一共有i 个，出去第一个最后一个，剩下 i-2
            for (int j = 0; j < i - 2; j++) {
                // j = 0 的时候，需要计算该行的第 2 个元素
                // 由上一行的第 1 个元素和第 2 个元素相加
                // j = 1 的时候，需要计算该行的第 3 个元素
                // 由上一行的第 2 个元素和第 3 个元素相加
                // 计算该行的 j + 2 个元素
                // 由上一行的 j + 1 个元素和 j + 2 个元素
                // 换成下标之后，统一减一
                // 上一行的 [j] 和 [j + 1] 的元素
                // 当前行的下标 [i - 1]，上一行的下标就是 [i - 2]
                // 先得到上一行
                List<Integer> prevLine = ans.get(i - 2);
                int first = prevLine.get(j);
                int second = prevLine.get(j + 1);
                int e = first + second;
                curLine.add(e);
            }
            // 该行的最后一个元素还是 1
            curLine.add(1);
        }
        return ans ;
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.generate(0));
        System.out.println(solution.generate(1));
        System.out.println(solution.generate(2));
        System.out.println(solution.generate(3));
        System.out.println(solution.generate(4));
    }
}
